package exam.test18;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Endstart
 * Date: 2020-12-18
 * Time: 23:05
 */
public class Tree {

    static class Node {
        int element;
        Node leftNode;
        Node rightNode;

        Node(int data) {
            this.element = data;
        }
    }

    public void checkAndRebuild(Node root) {
        Node leftNode = root.leftNode;
        Node rightNode = root.rightNode;
        int sumLeft = sum(leftNode, 0);
        int sumRight = sum(rightNode, 0);

        if (sumLeft < sumRight) {
            root.leftNode = rebuild(sumRight, leftNode);
        } else if (sumLeft > sumRight) {
            root.rightNode = rebuild(sumLeft, rightNode);
        }
    }

    private Node rebuild(int sumRight, Node node) {
        if (node == null) {
            return null;
        }
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node nodeTmp = queue.remove();
            nodeTmp.element = sumRight--;
            if (nodeTmp.leftNode != null) {
                queue.add(nodeTmp.leftNode);
            }
            if (nodeTmp.rightNode != null) {
                queue.add(nodeTmp.rightNode);
            }
        }

        return node;
    }

    private int sum(Node node, int number) {
        if (node == null) {
            return number;
        }
        number += node.element;
        number = sum(node.leftNode, number);
        number = sum(node.rightNode, number);
        return number;
    }


    public static void sort(int[] arrays) {
        Random random = new Random();
        boolean isOk = true;
        while (true) {
            isOk = true;
            for (int i = 0; i < arrays.length - 1; i++) {
                if (arrays[i] > arrays[i + 1]) {
                    isOk = false;
                    break;
                }
            }

            if (isOk) {
                return;
            }
            int randomCount = random.nextInt(arrays.length * 5) + arrays.length;
            for (int i = 0; i < randomCount; i++) {
                int s = random.nextInt(arrays.length);
                int t = random.nextInt(arrays.length);
                arrays[s] = arrays[t] + arrays[s];
                arrays[t] = arrays[s] - arrays[t];
            }

        }
    }

    public static void shuffles(int[] arrays) {
        Random random = new Random();
        for (int i = 0; i < arrays.length; i++) {
            int indexOne = random.nextInt(arrays.length);
            int indexTwo = random.nextInt(arrays.length);
            int tmp = arrays[indexOne];
            arrays[indexOne] = arrays[indexTwo];
            arrays[indexTwo] = tmp;
        }
    }

}
